Computing and Information Technology Interactive Digital Educational Library


Syllabus Collection >
Syllabus >

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 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 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:

File SizeFormat

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


Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback