Description
Course purpose: The course focuses on the ability to translate theoretical knowledge about algorithms, data structures, and complexity to efficiently be able to perform the complete process of analyzing a problem, estimate the running time of suggested solutions, and to implement a running program.
Learning Outcomes:
At the end of a successful completion of the course, the student
- knows algorithm design techniques, such as Greedy algorithms, Dynamic Programming, Exhaustive Search (brute-force)
- is able to analyze the performance of a proposed algorithm in big-Oh notation, and use this to estimate the running time of a program on a given computer on a given data set.
- is able to pick the right algorithm design technique and data structure for a given problem, and adapt these to new problems.
- is able to implement algorithms based on the covered design techniques.
- is able to recognize when one can use data structures for which standard library implementations exist, and make use of these data structures.
- is able to implement efficient data structures.
- is able to go from an algorithmic problem to an implementation of an efficient and correct algorithm for the problem.
Learning Outcomes:
At the end of a successful completion of the course, the student
- knows algorithm design techniques, such as Greedy algorithms, Dynamic Programming, Exhaustive Search (brute-force)
- is able to analyze the performance of a proposed algorithm in big-Oh notation, and use this to estimate the running time of a program on a given computer on a given data set.
- is able to pick the right algorithm design technique and data structure for a given problem, and adapt these to new problems.
- is able to implement algorithms based on the covered design techniques.
- is able to recognize when one can use data structures for which standard library implementations exist, and make use of these data structures.
- is able to implement efficient data structures.
- is able to go from an algorithmic problem to an implementation of an efficient and correct algorithm for the problem.
General Information
Lectures
CHEM 1171, Monday and Wednesday, 12:30-13:45
Office Hours
Daniel: HFH 2109, Tuesday 13:00-15:00
TA1:
TA2:
TA1:
TA2:
Section
Thursdays
13:00-13:50, PHELP1445
14:00-14:50, PHELP1445
15:00-15:50, PHELP2514
You may attend any section and any number of sections independently of which one you are assigned to. Bring your own laptop / tablet / something to program on.
13:00-13:50, PHELP1445
14:00-14:50, PHELP1445
15:00-15:50, PHELP2514
You may attend any section and any number of sections independently of which one you are assigned to. Bring your own laptop / tablet / something to program on.
Approximate Syllabus
We will cover a lot of the algorithms and data structures as seen in the Data Structures and Algorithms courses 130A and 130B ( DFS and BFS, Dijkstra, ... ), but with much less emphasis on proofs (I will prove things, but never ask you to prove anything!), and skipping the "how" of all data structures that are supported in standard language libraries (hash maps, balanced search trees). This will let us cover additional material, such as string algorithms, computational geometry, max flow. We will spend considerable time discussing implementation details to enable students to translate algorithmic ideas into code.
More detailed week to week topics covered are given in the Q&A "Course Schedule" post.
More detailed week to week topics covered are given in the Q&A "Course Schedule" post.
Recommended prerequisites
I do not enforce any prerequisites. However, you will have a hard time in the class if you do not have a firm grasp of the concepts from CS40 and are quite comfortable with the basics of programming (recursion, use of standard libraries, object oriented programming, ... ). I will proceed as if you know this! You are welcome to use off-lecture resources such as office hours, sections, Piazza questions, to help brush up on concepts you need.
Textbooks
No textbook is mandatory, here are two books that cover (almost) everything in this course and a lot more:
Competitive Programmer's Handbook ( https://cses.fi/book/book.pdf )
Competitive Programming ( https://cpbook.net/ )
Competitive Programmer's Handbook ( https://cses.fi/book/book.pdf )
Competitive Programming ( https://cpbook.net/ )
| Name | Office Hours | |
|---|---|---|
Daniel Lokshtanov | When? Where? | |
Songyin Wu | When? Where? | |
Ryan Keeney | When? Where? | |
Anikait Mundhra | When? Where? | |
Vaishali Surianarayanan | When? Where? |