CPSC 335 Information Structures II

Contents

• Textbook and recommended reading
• Course information
• Course outline
• Code examples
• Course evaluation
• Assignments
• Useful links
• Course policies

NOTE: ALL QUESTIONS regarding assignments (specifications, code, marking) should be directed to your TAs Faisal Ahmed and Madeena Sultana.
You can send an e-mail or make an appointment to met your TA in person if you need any help with your program, report or an algorithm.

Course Textbook

1. Data Structures and Algorithms in Java, Adam Drozdek, 2nd Ed, Nelson Education 2005 edition (other editions are acceptable)
2. Data Structures and Algorithms in Java, C. Shaffer, 3rd Ed, Dover Books, 2011

Recommended Reading

1. Introduction to Algorithms Cormen, Lieserson, Rivest, Stein Mc Graw Hill

2. Data Structures and Algorithm Analysis in Java Mark Allen Weiss, Peachpit Press

3. Algorithms in Java, Robert Sedgewick, Michael Schidlowsky, Addison Wesley Professional

Java Books (additional resources)

1. Java by Dissection by Ira Pohl and Charlie McDowell
2. Java Programming from the beginning K.N. King, Norton and Company
3. Java - A Framework for Programming and Problem Solving K. Lambert, M. Osborne Brooks/Cole

Course Information

Computer Science 335 Information Structures II

Collision resolution in hash tables, search algorithms, advanced tree structures, strings. Advanced algorithmic tools for storing and manipulating information. A comparison of programming paradigms.

Prerequisites: CPSC 331

Objectives and Outcomes

It is expected that students have basic procedural and object-oriented programming skills, as introduced in the courses CPSC 231, 233 and 331. Since Pascal, Java and C/C++ are the programming languages that students were made familiar with, it is expected that students are familiar with these languages. Students should also be familiar with the data structures that are introduced in the prerequisite course CPSC 331.

CPSC 335 continues CPSC 331 by introducing additional tools and skills that are needed to solve problems by computers, through the development of programs using high-level programming languages. It introduces algorithms that can be used to solve several fundamental problems as well as data structures that are commonly used to manage information when solving problems of small-to-moderate size. It also uses the terminology and notation that is commonly used in computer science for the analysis of algorithms.

The course introduces advanced data structures, such as dynamic hashing, B*, B+, red-black trees, advanced algorithms on graphs and path finding techniques, memory management, data structures for storage and compression, string algorithms, and some computational problems.

Students are required to write programs using the above algorithms and data structures on assignments, to perform experiments involving the execution of their programs on large sets of data in order to assess the performance of their algorithms, and to use very simple analytic techniques to assess the performance of simple fragments of code.

Please note that learning to program is a very time-consuming activity and assignments in this course may well take more time to complete than assignments in other courses. The course emphasizes student activity. This means that a significant portion of what you learn will come from working on the assignments and programming independently.

Course Outline

Week 1

     History of Algorithms. Algorithm design on conceptual level. Data structures review.

    Data structures: stacks, queues, trees, heaps, hashing, graphs (Chapters 2, 3, 4, 5, 8 of the textbook 1)

See notes from CPSC 331 (prerequisite) course on simple sorts, complex sorts, heaps, graph1,  trees1, trees2  
Lecture on History of Algorithms
Lecture on Data Structures Overview

Week 2

        Hashing, Dynamic hashing (Ch. 10 textbook 1, Ch. 11 recommended text 3) See notes on simple_hashing. 

        Hashing lecture.  Perfect hashing. Dynamic Hashing lecture.

Week 3

        Coalesced hashing, non-static hashing: Brent's, binary tree methods

        (Ch. 10 textbook 1, Ch. 11 recommended text 3)

        Coalesced and Brent's lecture   Handout given in class.

Week 4

         Hashing review questions. Trees - self-test.   

    Trees: balanced B, B*, B+  (Ch. 6-7 textbook 1, Ch. 12-13 recommended text 3)
    See notes on Btree1, Btree2
    Lecture on  Tree Applications and Text on Trees and Internet Search
   Insertion into B tree -example

   Deletion from a B tree -example

Video: 14.300 Motivation for Index Structures, Selectivities, Scan vs. Index Access on Disk and Main Memory

 Week 5

     Trees continues: 2-4, horizontal-vertical, red-black, AVL, IPR  (Ch. 7 text, Ch. 12-13 recommended text 3)
     Lecture on general trees, B tree variants, 2-4 trees
     Lecture on balanced trees
        

WEEK 6  - READING WEEK, NO CLASSES

Week 7

Tree review questions
       AVL-IPR exercise
       IPR demo
       Sedgewick red-black tree

Midterm Exam is scheduled
 

Week 8

     Searching: binary, for game programming, lecture on binary and spatial space partitioning
    (Ch 13 recommended text 3, Ch. 12-13 recommended text 5).

     BSP - binary space partitioning, including k-d, interval, grid, quad-trees and R trees. (Ch. 7 text, Ch. 12-13 recommended text 3)

kd trees
Spatial Trees
Grid in-class handout

Spatial BKD tree searches for points inside London, UK

Grid File

Week 9

Lecture on tries and search
min-max article and minimax wiki
Web search lecture

Week 10

       Compression (Ch 11 of textbook).

Huffman decoding no look-ahead
Huffman decoding research
Shannon-Fano definition

Web crawling.
Reddit "hotness" algorithm  Open-source code

Week 11

Dynamic programming. String matching. DNA Matching.

Video 0/1 Knapsack Problem -- Dynamic Programming

Randomized algorithms lecture.

Video Traveling Salesman Problem Visualization

Linear programming. (Ch. 29, Ch.15  recommended text 3).

Backtracking. (Ch. 32 recommended text 3)

Week 12

Tuesday   "CAD/3D Car Designs of the Future"

Thursday  Class visit and live demo of biometric security algorithms

Tuesday  Guest lecture Prof. Greg Hagen: "Introduction to Intellectual Property and Privacy Law for Computer Scientists."

Bio: Greg Hagen is an Associate Professor, Associate Dean (Research) and Graduate Program Director in the Faculty of Law. His area of research is intellectual property and technology law, including information technology, security and privacy law. He is a member of the Institute for Security Privacy and Information Assurance at the University of Calgary. He is also a member of the Law Society of British Columbia.

Thursday Applications of algorithms. Interactive in-class activity.
  Lecture on geometric algorithms in robotics, motion planning and optimization
  Image processing, simulation, biometric security. 

Week 14

Final review. TUTORIAL Q&A SESSION.   

Course Evaluation

Three components are included in the determination of the course grade:

Assignment           30%

Midterm exam      30%

Final exam           40%

Missed Components of Term Work: The regulations of the Faculty of Science pertaining to this matter are found in the Faculty of Science area of the Calendar. Section 3.6. It is the student’s responsibility to familiarize themselves with these regulations. See also Section E.6 of the University calendar.

Labs

The lab work and assignments are considered to be essential components of the course. Completed assignments should be submitted electronically to your TA. Remember to put your name, lab section and your TA's name on any material you hand in.

Assignments

There will be four programming assignments in this course. Each assignment is to be submitted on the due date. Please consult your TA web site on late submission policies and exceptions.

Assignment 1 Extendable Hashing

Dynamic Hashing Large data set
Data set from Chapter 8.2, Horowitz textbook

Assignment 2 Indexing and Multiway Trees

Sample data set: Input 1 

Assignment 3 Dictionary

Sample data sets:

Dictionary file
File to check spelling

Assignment 4 Compression

Sample data sets:

File to compress1 (dictionary file)
File to compress2

335tester.zip --> contains java code to read and dump information from a c335 file.

335decompressor.zip --> a decompressor exe file, that students can use to decompress the files they compressed with their program. usage: c335 -d sourcefile targetfile

huffman335 file

Cheating on assignments and/or exams will result in penalties which may include a 0 mark on the assignment component, failing the course and expulsion from the faculty and university (see Plagiarism/Cheating/Other Academic Misconduct sections of the university calendar).

Access to Computers and Help

Each of you has been assigned two labs per week. TAs will provide help with the assignments. Since TAs for this course spend most of their required time in the lab, you should go to the lab for help rather than seeking out TAs in their offices.

General Notes

If you encounter problems in the lab that your TA can not resolve, or if you want to discuss the operation of the labs, please contact the Instructor. You should contact your Instructor to discuss lectures, exams and the overall organization of the course. In this course, you are always welcome to ask questions if you don't understand something during the lecture or in the lab. You can also always contact your instructor during office hours or any time by e-mail. Some of the exercises and assignments may require a reasonable amount of time to complete. You will find that you need to spend time on the computer outside of your regularly scheduled labs, and this is the way the course is designed.