CS146 OverviewProblem Solving by ComputingLanguages, Levels, Virtual MachinesSlide 5What is an Algorithm?Sorting ProblemSimple Sorting AlgorithmsSlide 9Insertion SortPowerPoint PresentationLatent Semantic IndexSlide 13Slide 14CS146 OverviewProblem Solving by ComputingHuman Level Virtual Machine Actual Computer Virtual Machine Level L0Languages, Levels, Virtual MachinesA multilevel machineLanguages, Levels, Virtual MachinesProblem Solving by ComputingHuman Level (Algorithms) Machine Level Ln(JAVA )What is an Algorithm?An algorithm is a well-defined computational procedure that takes some value or set of values, as input and produce some value or set of values as output. A “tool” for solving a well-specified computational problemSorting ProblemInput: A sequence of numbers (a1, a2, . . .)Output: A reording (a’1, a’2, . . .) of the input such that a’1 a’2 . . .Simple Sorting Algorithms1. Insertion Sort2. Merge Sort 3. Quick SortSimple Sorting Algorithms1. Insertion Sort2. Merge Sort 3. Quick SortInsertion Sortj 2 to length[A] Do A[j] key insert A[j] into A[1, 2, … j-1] i j-1 While i > 0 and A[I]> key Do A[i+1] A[i] i i-1 A[i+1] key5 2 4 6 1 3j=22i=j-1=1 Key=2A[1]>key 1>05 2Latent Semantic IndexProject:Compute the LSI (Latent Semantic Index) of a set of web pages/text files, such as Google’s return.Sort a web page or a text file (XML or Text) in alphabetical orderLatent Semantic Index1. Sort a web page or a text file (XML or Text)2. Create an Inverted file Attached to each words a list of locations that this word has appearedLatent Semantic Index1. Applications2. Use LSI, we can cluster (classify) the return of Google’s search into meaningful
View Full Document