Last revised November 15, 2018

List of major topics that will or may be covered by Test 1 (common for CSC 501 and CSC 401) All these topics will or may be covered by Test 2 and Final Exam, too.

This list, although fairly extensive, is not supposed to be complete. Consult your class website, pages: Syllabus, Course Outline,  Notes, Homework, and Tests for the complete information.

You may be asked to solve any of the posted homework problems that pertain to the covered material.

You may be asked to compute any formula in file  http://csc.csudh.edu/suchenek/CSC401/Mathematica/Summationa.nb
After all the commands in that file are executed (by moving the cursor into the command and pressing Shift-Enter), the file contents should look like this:
http://csc.csudh.edu/suchenek/CSC401/Mathematica/Summationa.pdf

You may be asked to reproduce the derivation in file http://csc.csudh.edu/suchenek/CSC401/Mathematica/Proof_floorLog2eqCeilLog2Plus1.nb

You may be asked to give definitions in file http://csc.csudh.edu/suchenek/CSC401/Mathematica/WorstAvgRunTime.nb

You may be asked to give definitions and properties in file http://csc.csudh.edu/suchenek/CSC401/Mathematica/BigOh1.nb

and in file http://csc.csudh.edu/suchenek/CSC401/BigOh_big_Theta.pdf

You may be asked to compute or quote any formula in file http://csc.csudh.edu/suchenek/CSC401/Mathematica/BigTheta_Summation.nb

You may be asked to compute or quote or derive any result in files http://csc.csudh.edu/suchenek/CSC401/Mathematica/LowerBoundsUpperBoundsFindMax.nb
http://csc.csudh.edu/suchenek/CSC401/Mathematica/WorstTimeSeqSearch.nb
http://csc.csudh.edu/suchenek/CSC401/Mathematica/AvgerageTimeSeqSearchUnordered.nb
http://csc.csudh.edu/suchenek/CSC401/Mathematica/AverageTimeSeqSearchOrdered.nb
http://csc.csudh.edu/suchenek/CSC401/Mathematica/WorstTimeBinSearch.nb
http://csc.csudh.edu/suchenek/CSC401/Mathematica/WorstCaseOptimalityBinSearch.nb
http://csc.csudh.edu/suchenek/CSC401/Mathematica/AverageTimeBinSearch.nb
and http://csc.csudh.edu/suchenek/CSC401/Mathematica/AverageCaseOptimalityBinSearch.nb

You may be asked to quote or derive formulas for the minimum internal path length (ipl) and the minimum external path length (epl) in a binary tree on n nodes.

You may be asked to compute or quote or derive any result in files http://csc.csudh.edu/suchenek/CSC401/Mathematica/InsertionSortAvgTime.nb
http://csc.csudh.edu/suchenek/CSC401/Mathematica/InsertionSortWorstTime.nb
and http://csc.csudh.edu/suchenek/CSC401/Mathematica/InsertionSortOptimality.nb

You may be asked to compute or quote or derive any result in file http://csc.csudh.edu/suchenek/CSC401/Mathematica/Average-case_Quicksort.nb

The following topics will NOT be covered by Test 1.
However, they will or may be covered by Test 2 and Final Exam.

You may be asked to compute or quote or derive any result in file http://csc.csudh.edu/suchenek/CSC401/Slides/Worst-caseMergesort.pdf
with picture being corrected in flie http://csc.csudh.edu/suchenek/CSC401/Slides/RecursionTreeFixed.jpg

You may be asked to compute or quote or derive any result in file http://csc.csudh.edu/suchenek/CSC401/Slides/Excerpts_from_Knuth-Suchenek_formulas.pdf

The 2-trees as covered in files http://csc.csudh.edu/suchenek/CSC401/Slides/2-trees.pdf
http://csc.csudh.edu/suchenek/CSC401/Slides/Internal_External_Path_Length.pdf
and http://csc.csudh.edu/suchenek/CSC401/Slides/BS_decision_tree_slides.pdf
are likely to be covered thoroughly on the Test 2 and Final Exam.
Here is a link to a companion file that is supposed to help you studying them:
http://csc.csudh.edu/suchenek/CSC401/Slides/2-trees_companion_notes.pdf

You may be asked to compute or quote or derive any result in files http://csc.csudh.edu/suchenek/CSC401/Mathematica/LowerBoundAverageCaseSorting.nb
and http://csc.csudh.edu/suchenek/CSC401/Slides/Worst-case_lower_bound_on_sorting_by_decision_tree.pdf



Good luck!