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.
Course Format: 2 lectures (75 minutes each) per week. There will be one fairly extensive auto-graded programming assignment due every week. Programming assignment problems are as encountered in programming competitions (such as the ACM ICPC) or on programming challenge sites (such as Codeforces, Leetcode, or Kattis). To pass the course you will need to pass all the programming assignments. There might also be a small number of programming competitions with mandatory attendance.
Curriculum: 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.
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.
Recommended prerequisites:
Roughly CS40 and CS32 -- while I will not enforce any prerequisites, 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, ... )
Note: apart from the recommended prerequisites above, GOLD does not have enforced prerequisites or enforced restrictions on this course.