CITIDEL >
Syllabus Collection >
Syllabus >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10117/5608

Title:  ECS 110 
Authors:  Computer Science @ UC Davis 
Issue Date:  
Publisher:  Computer Science @ UC Davis 
Citation:  http://www.cs.ucdavis.edu/~rogaway/classes/110/spring97/syllabus.html 
Abstract:  Note. This lecturebylecture 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, gametrees, and branchandbound.
ECS 110  List of Lecture Topics
Lecture Topic
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 BigO.
............. F 4/4 hw0 due at 11:59 pm
Week 2 Lect 3  T 4/8 Analysis of changemaking 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/postorder 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 BTrees. 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): 46 pm, 55 Roessler
............... R 5/7 Section B Final (Matthews): 810 am, 55 Roessler 
URI:  http://www.citidel.org/handle/10117/5608 
Appears in Collections:  Syllabus

Files in This Item:
File 
Size  Format 
26syllabus.html  4Kb  HTML  View/Open 

All items in DSpace are protected by copyright, with all rights reserved.
