Wolf Bein

CS 302 Introduction to Data Structures


ANNOUNCEMENTS




Posted 01-17-19:
The pages for this course are now ready. The syllabus is subject to change.


Posted 01-17-19:
If you do not have an account in the lab yet: Here is the account application.


Posted 01-17-19:
For assignment 1: Complex numbers explained. Also, headers, output, and code snippets for assignment 1.


Posted 01-17-19:
Seiden's Theoretical Computer Science Cheat Sheet.


Posted 01-17-19:
Current Reading: 1.4 - 1.7 in the 45 page handout, Chapter 2.



Posted 01-28-19:
Here are the office hours of our TA, Ms.Shradha Kapoor, kapoos1@unlv.nevada.edu:
Monday 1:00 pm - 2:00 pm
Tuesday 10:00am - 11:00 am
Wednesday 4:00 pm - 5:00 pm
The office hours will be held in lab TBE B346.
As announced in class today only <(Monday, January 28) Mr. Kaushik Deshmukh, will substitute for Ms. Kapoor in lab TBE B 361.


Posted 01-31-19:
Here is the Big-Oh Slide.


Posted 01-31-19:
Linked Lists: Reading is 3.5 and 3.6, see 45 page handout , the code is here list_class.cxx
How to generate random numbers.


Posted 02-07-19:
This is how to print the list:
for(ni=the_List.begin(); ni!=the_List.end(); ni++) { cout << *ni << " "; }


Posted 02-07-19:

For assignment 3, here is how to measure the run of your program:

You need to use the command time. The syntax for using time is
time ./a.out
The output for time will have three lines like these.
real 59.95
user 55.24
sys 0.09
Use is the one called `user'. (55.24 in the example below.)
The other ones (real, sys) take operating system overhead
into account.



Posted 02-07-19:
Here is the Master Theorem.


Posted 02-07-19:
Current Reading: Chapter 3.


Posted 02-14-19:
Exam 1 will be on Friday, March 1.


Posted 02-21-19:
Current Reading: 4.1, 4.2.


Posted 02-21-19:
More on Postfix Expressions.


Posted 02-21-19:
Note that substraction and division do not commute, ab/ means a/b and not b/a (similarly ab- means a-b).
Here are a few more examples to test your program:
4572+-*$ -16
34+2*7/$ gives 2
57+62-*$ gives 48
42351-+*+$ gives 18
42+351-*+$ gives 18



Posted 02-21-19:
Here is a simple function to convert a character, which represents a number to a n integer value: int CharToInt(const char c)
{
switch (c)
{
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '3': return 3;
case '4': return 4;
case '5': return 5;
case '6': return 6;
case '7': return 7;
case '8': return 8;
case '9': return 9;
default: return 0; }
}



Posted 02-21-19:
Reminder: The first midterm is on Friday, March 1.
Reading (study guide) for the first midterm.

Study Guide
Chapter 1 (Math and Code review)
Chapter 2 (Algorithmic Complexity).
Chapter 3: 3.1,3.5 (Lists), 3.6 (Stacks), 3.7 (Queues).
Chapter 4: 4.1 (Trees)
Chapter 7: 7.1, 7.2 (Insertion Sort).
Review assignments 1 - 5.


Posted 02-22-19
There is a typo in Assignment 5. It is due Saturday March 2.


Posted 02-27-19:
Here are the solutions for assignment 4.


Posted 02-28-19:
Here is the dot-h file TaskTree.h for assignment 6. Additionally, here is main.cxx.
You may modify the files.
Here is a code snippet to set up the tree and another code snippet which shows you how to print out such a tree in preorder. Here are constructors.


Posted 03-07-29
Office Hours 12:30 pm - 2:30 pm, March 8 are cancelled.


Posted 03-14-19:
Reading: 4.3, 4.4, 4.7, and 4.5, Splay Trees.
Exam 2 will be on Friday, April 12.


Posted 03-22-19:
Here are the AVL Tree Notes.

Following is the extra reading on Splay Trees:
1. Read 4.5 (Splay Trees) in our text book.
2. Study the following Splay Tree Notes.
3. Look at 11.5 which discusses amortized run time analysis for splay trees.


Posted 03-31-19:
Here are the 2-3 Tree Slides.


Posted 04-04-19:
Here is the Binary Search Tree code.


Posted 04-04-19:
Milestone design component (roughly one page in length):
- design document
- data structure used and how they were implemented; explain why the use of these structures fosters efficiency.
- what machine used to compile and run
Here are prointers for a good design document. As discussed our design documents will be somewhat simpler.


Posted 04-04-19:
Reminder: The second midterm is on Friday, April 12.
Reading (study guide) for the second midterm.

Study Guide
Chapter 4: 4.1 (Tree Traversals), 4.2 (Binary Trees), 4.3 (Binary Serach Trees), 4.4 (AVL Trees)
Chapter 6: 6.1, 6.2, 6.3 (Heaps), 6.4 (Event Simulation), 6.8 (Binomial Trees), 6.9 (Priority Queues).

Review: Assignment 6 (Tree Traversals), assignment 7 (Binary Search Trees, AVL Trees), assignment 8 (Binary Search Tree Sort), assignment 9 (Airport Simulation).



Posted 04-11-19:
Office hours on Friday, April 12, will be from 2:00 pm to 3:00 pm and the office hours on Thursday, April 18 will be from 3:00 pm to 5:00pm due to thesis defenses.



Posted 04-24-19:
Lecture notes: delete and merge with Binomial Heaps.




Posted 04-25-19:
Fun with sorting: Dance routines for
mergesort, quicksort, and heapsort. As well Super Mario Heapsort Here slowsort visualization.


Posted 04-25-19:
Here is an example graph and the text file text file for Assignmemt 12.


Posted 05-10-19:
The final is on Friday, May 17, 10 am - 12:00 pm. It is comprehensive.
Reading:
Chapter 1
Chapter 2
Chapter 3
Chapter 4: 4.1, 4.2, 4.3, 4.4, 4.6, 4.7,
Chapter 5: 5.1, 5.2, 5.3, 5.4, 5.5
Chapter 6: 6.1, 6.2, 6.3, 6.4, 6.8
Chaper 7: 7.1, 7.2, 7.3, 7.6, 7.5, 7.7, 7.9
Chapter 8: 8.1, 8.2, 8.3, 8.4
Chapter 9: 9.1, 9.2, 9.5, 9.6
Review assignments 1 - 12.