CSCI 260: Data Structures and Algorithms

Prerequisites:

Course Motivation and overview

It is assumed the student has a reasonable mastery of C++ or a similar high level language, as the course will involve substantial work implementing the data structures under discussion. C++ will be the language of implementation. Students whose previous experience has been in Java or another imperative language are advised to familiarize themselves with C++, with memory allocation and pointers in particular. As well, the student should have a familiarity with the discrete mathematical concepts introduced in Math 123, such as graphs, Big-O notation, logarithms and powers, counting, and logic.

The course will focus on the concepts of abstract data types (ADTs), developing correct and efficient algorithmic solutions to computational problems, analysis of time and space efficiency, and proving correctness of algorithms.

Course materials

• Text: There is no printed text required for the course. Students should take good notes, and web materials will be posted to the site indicated above.
  
  Students may nevertheless find books useful. A number of Data Structures and Algorithms books are available for loan from the Computing Science bookcase (outside office 211 in Building 315).
  Also, the following is an excellent auxilliary, and more advanced, text: Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms(ISBN 0-07-013151-1). An earlier edition (minus author Stein) is in the VIU library.
  
  Two other good texts are the book Algorithms by Robert Sedgewick and Kevin Wayne, and Data Structures, Algorithms, and Applications in C++ by Sartaj Sahni.
  
  
• Web texts
  The following text for a similar course online and freely-available:
  • Web material: some lecture notes, assignments, tutorials, sample programs, practice problems, etc, may be made accessible through http://csci.viu.ca/~gpruesse/teaching/260/
  • http://people.cs.vt.edu/~shaffer/Book/C++3elatest.pdf. For more information about the text and opportunity to obtain a print copy, follow this link.
  • Open Data Structures text

Timetable

• Lectures: Mo We 14:30-16:00, Th 16:00-17:00 Bldg 370, Room 111
  
• Labs in 315/115: Th 12:30-13:30 OR 14:30-15:30.
• Office Hours: Mon 12:00-1:00, We 16:00-17:00
  

Assessment:

1. achieve an average of 50% or greater on the weighted average of the midterms, submitted material (labs and assignments) and the final exam; and
2. achieve a grade of 50% or greater on the final exam; and
3. attend the labs and submit the lab work, and pass the graded lab assignments.

1. Midterm 1: October 6
2. Midterm 2: October 27
3. Midterm 3: November 24

• 30% midterms
• 40% final
• 30% submitted assignments including programs

Submitting material
Programs must work on the csci linux platform. Students should submit their text files containing their code according to the procedure that will be given in the lab. Git will be used.

Topics to be covered

• Review: logarithms, proof techniques
• Big Oh notation; Big-Omega, Big-Theta.
• The Master Theorem
• Analysis of algorithms: straight-line code, loops, recursion
• Algorithm correctness; proofs of, using mathematical induction.
• Abstract Data Types
• Dictionary ADT
• Hashing
• Binary Search Trees and balancing techniques
• B-Trees
• Divide and Conquer Algorithms and their analysis
• Searching and sorting algorithms
• Graph representations
• Graph traversal algorithms: breadth-first and depth-first search
• Shortest paths algorithms: Dijkstra
• Dynamic Programming
• Greedy Algorithms
• Union-Find algorithms

Attendance:

Students are expected to attend scheduled lectures, laboratories, field trips, seminars, examinations, practica and work experience. The University reserves the right to cancel registration in any course or program because of lack of attendance (where attendance is deemed by the Department to be important). VIU reserves the right to cancel any student’s registration in a course if the student does not attend the first scheduled session of a course and does not notify the instructor or area secretary.
Absenteeism
Students are responsible for all material presented and discussed in lecture, in addition to assigned readings and homework problem. It is entirely the students' responsibility to recover any information or announcements presented in lectures from which they were absent by speaking to their fellow students.

Students who are absent should contact their instructors as soon as possible and report to their instructors again on return to classes. Extended absence from courses or program should be discussed with each instructor or program coordinator involved. Students are responsible for contacting their instructors, either directly or through the assistance of staff in the office of the appropriate Dean, as soon as an extended absence becomes apparent.

Specific regulations exist for absences due to illness, death in the family, religious observances, and VIU official sporting teams. In cases of religious observance and sporting events, discussion on the impact of your absence with your instructor need to occur at least two-weeks in advance of the absence.
Absence Due to ...
Attendance
Policy 96.05

Academic Integrity Statement
It is expected that students will know and abide by the VIU's policy on Student Academic Code of Conduct (Policy 96.01)

Standards of Academic Integrity
Include, but are not limited to:

• independently producing work submitted under their own name;
• all graded work needs to be written independently, unless expressly instructed to collaborate.
• properly and appropriately referencing all work;
• identifying all collaborators in work;
• completing examinations without giving or receiving assistance, excepting those students requiring assistance due to a documented accessibility issue;
• the use of tutorial services, including online sites, to solve graded work is strictly prohibited.
• the use of online sites and apps for solving mathematical problems on graded work is strictly prohibited.
• respecting the integrity of examination materials and/or the examination process; and respecting the integrity of computer security systems, software copyrights and file privacy of others.