Syllabus Collection >
Please use this identifier to cite or link to this item:
|Title: ||ECS 110|
|Authors: ||Computer Science @ UC Davis|
|Issue Date: |
|Publisher: ||Computer Science @ UC Davis|
|Abstract: ||Note. This lecture-by-lecture syllabus is being maintained by Phil Rogaway and will be accurate for his class. But John Matthews and I are keeping the two sections close to being in synch, so the syllabus should be reasonably accurate for his class, too. Lecture 20 did differ between Matthews' and Rogaway's section: Matthews' lecture 20 was on search techniques such as backtracking, game-trees, and branch-and-bound.
ECS 110 - List of Lecture Topics
Week 1 Lect 1 - T 4/1 Introduction. Implementation and fundamental types. ADTs. Associative arrays. A first C++ program.
Lect 2 - R 4/3 Making change in Bhutan. Memoization. Time complexity. Theta, Omega, and Big-O.
............. F 4/4 hw0 due at 11:59 pm
Week 2 Lect 3 - T 4/8 Analysis of change-making algorithms. Implementation of associative arrays.
Lect 4 - R 4/10 The String ADT. More C++ discussion. Finite automata.
Week 3 Lect 5 - T 4/15 Fast implementation of Find using FA. Stack ADT and implementations of stacks. C++ quiz.
Lect 6 - R 4/17 Uses of stacks - paren matching, maze exploration, postfix evaluation, infix -> postfix.
............. F 4/18 hw1 due at 11:59pm
Week 4 Lect 7 - T 4/22 Comments on hw1. Survey. Uses of stacks. Queues (as an ADT; uses; cf. stacks; implementations).
Lect 8 - R 4/24 Contest winners. Flavors of lists. LISP lists. Binary trees. Expression trees. Pre/in/post-order traversal.
Week 5 Lect 9 - T 4/29 (John Matthews lecturing.) Binary search trees.
Lect 10 - R 5/1 Ways to maintain balance. Splay trees. Amortized analysis.
............... F 5/2 hw2 due at 11:59pm
Week 6 Lect 11 - T 5/6 Midterm
Lect 12 - R 5/8 Hashing. Collision resolution. Perfect hashing. Universal hashing.
Week 7 Lect 13 - T 5/13 Program checking (sorting; using universal hashing). Priority Queues. Heaps. Binary heaps. Heapsort.
Lect 14 - R 5/15 Lazy binomial queues, Fibonacci heaps (including amortized analysis of).
Week 8 Lect 15 - T 5/21 Insertion sort, Shell sort, mergesort, quicksort, bucket sort, radix sort. Lower bound.
Lect 16 - R 5/23 Graphs (definitions about, sample problems on, representations of). Dijkstra's algorithm.
............... F 5/24 hw3 due at 11:59pm
Week 9 Lect 17 - T 5/27 Running time of Dijkstra's algorithm using different data structures. DFS, BFS.
Lect 18 - R 5/29 Uses of DFS, BFS. MSTs - Prim's algorithm. HW3 Contest results. Evaluations.
Week 10 Lect 19 - T 6/3 Kruskal's algorithm. Disjoint Sets ADT and the Union/Find data structure.
Lect 20 - R 6/5 B-Trees. Digital search trees. Binary tries. Patricia. Tries. Huffman codes. Lessons, bye!
............... F 6/6 hw4 due at 11:59pm
Week 11 ............... W 5/6 Section A Final (Rogaway): 4-6 pm, 55 Roessler
............... R 5/7 Section B Final (Matthews): 8-10 am, 55 Roessler|
|Appears in Collections:||Syllabus|
Files in This Item:
All items in DSpace are protected by copyright, with all rights reserved.