Dr. Anwar Mamat
E-Mail: anwar@temple.edu
Office Location: Room 317 of SERC
Phone: 215-204-4207
Office hours: Tuesday,Thursday 1:00-2:00pm or by appointment
Yiyi Zhu
Office: 415 wachman hall
Office Hours: Wed. 3-5pm
Email: yiyi.zhu@temple.edu
Phone: 2158581026
Lectures: Tuesday, Thursday9:30 AM – 10:50AM, Tuttleman Learning Center 403B
Lab: Wednesday 1:00 PM – 2:50 PM, SERC 206
At least a C- in CIS 1068.
The course introduces basic data structures, like linked lists, stacks, queues, trees and sets. Applications given as JAVA programming assignments will motivate the need for these abstract data types to implement algorithms efficiently. The second part of will introduce important algorithms, which build the basis of many applications. Among these concepts will be recursion, sorting algorithms (insertion sort, mergesort, heapsort, quicksort), and algorithms to traverse or organize data structures (balancing trees). Although the course is not an introduction to JAVA programming, JAVA will be used as an example for a modern, object oriented language. The course will closely follow the structure of the textbook.
Textbook (recommended, not required)
Data Structures: Abstraction and Design Using Java, Second Edition Elliot B. Koffman, Paul A. T. Wolfgang Wiley 2010, ISBN: 978-0-470-12870-1
Algorithms, 4th edition, Robert Sedgewick, Kevin Wayne, Addison-Wesley, 2011
Introduction to Programming in Java, Robert Sedgewick, Kevin Wayne Addison-Wesley, 2008
Grading
Assignments |
50% |
Expect 10 assignments |
Midterm |
15% |
|
Final |
25% |
Cumulative Final |
attendance, quizzes |
10% |
Expect a quiz every week |
There will be a series of programming assignments (10 assignments). You must write each program yourself but are encouraged to obtain help - from fellow students, the laboratory instructor or the instructor - to get to the point that you can do so. The assignments are to be handed in on time or credit may be lost. You may develop the programs on any system but the program must end up on our system so it can be accessed, edited, and run in the laboratory.
Week 1: Java Review: Class, Inheritance, Polymorphism, Abstract Classesm, Abstract Methods
Week 2: Array based containers, Bag and SortedBag, Comparables and Iterators, Generics
Week 3: Linked Lists, Nodes, single linked list, double linked list
Week 4: Big-O notation, runtime Analysis examples, Iterators, More Generics
Week 5: Stacks & Queues; LIFO vs FIFO, Stack example: Expression Evaluation
Week 6:Recursion; recursive problems, the role of the stack in recursion, recursion vs iteration
Week 7:Trees, Binary Trees, Huffman Trees,
Week 8: Midterm, Review and Exam
Week 9: Trees: Binary Search Trees (BST), basic operations of BSTs, complexity analysis of BSTs.
Week 10 Priority Queues, Heaps, Set, Map
Week 11: B-trees, 2-3-4 Trees
Week 12 Hash tables: Open addressing, linear probing, quadratic probing, chaining. Reasoning about hash functions.
Week 12: Sorting: Insertion, Bubble, Selection, Heap, Merge, Quick.
Week 13: Graphs, Graph Representations, Undirected Graphs, Directed Graphs, Traversal, DFS, BFS
Week 14: Graphs: Minimum Spanning Trees, Shortest path algorithm
Week 15: Regular Expressions
Policies and Rules