algorithms

Unix File System Unix allows a user to group related files within a directory. Suppose we want to work with two different applications, one involving documents and the other involving images. May be we group the document related files under one directory and image related files in another directory. Sometimes it helps to further subdivide files. Unix allows creation of sub-directories to help organise files hierarchically. Such a file organisation creates a tree of directories with files as leaves. When you log into a Unix system you always do so in your login directory. You may create files as well as subdirectories starting from the login directory. A n example of file hierarchy: When I created course notes for web browsing, I first created a directory COURSES under my home directory. Under this directory I created directories called OS, SE, COMPILERS respectively for operating systems, software engineering and compiler courses. You may browse the course pages at the URL http://

Branch and Bound Searching Strategies Feasible Solution vs. Optimal Solution • DFS, BFS, hill climbing and best-first search can be used to solve some searching problem for searching a feasible solution. • However, they cannot be used to solve the optimization problems for searching an (the) optimal solution. The Branch-and-bound strategy • This strategy can be used to solve optimization problems without an exhaustive search in the average case. • 2 mechanisms: – A mechanism to generate branches when searching the solution space – A mechanism to generate a bound so that many braches can be terminated • It is efficient in the average case because many branches can be terminated very early. • Although it is usually very efficient, a very large tree may be generated in the worst case. • Many NP-hard problem can be solved by B&B efficiently in the average case; however, the worst case time complexity is still exponential. Bounding • A bound on a node is a guarantee that a

C o ping with the Limitations of Algorithm Power Tackling Difficult Combinatorial Problems • There are two principal approaches to tackling difficult combinatorial problems (NP-hard problems): • Use a strategy that guarantees solving the problem exactly but doesn’t guarantee to find a solution in polynomial time • Use an approximation algorithm that can find an approximate (sub-optimal) solution in polynomial time Exact Solution Strategies • ex haustive search (brute force) – useful only for small instances • dynamic programming – applicable to some problems (e.g., the knapsack problem) • backtracking – eliminates some unnecessary cases from consideration – yields solutions in reasonable time for many instances but worst case is still exponential • branch-and-bound – further refines the backtracking idea for optimization problems Backtracking • Suppose you have to make a series of decisions, among various choices, where – You don’t have enough information to know

Limitations of Algorithm Power Objectives We now move into the third and final major theme for this course. 1. T ools for analyzing algorithms. 2. De sign strategies for designing algorithms. 3. Identifying and coping with the limitations of algorithms. Efficiency of an algorithm • By establishing the asymptotic efficiency class • The efficiency class for selection sort (quadratic) is lower. Does this mean that selection sort is a “better” algorithm? – Like comparing “apples” to “oranges” • By analyzing how efficient a particular algorithm is compared to other algorithms for the same problem – It is desirable to know the best possible efficiency any algorithm solving this problem may have – establishing a lower bound Lower Bounds L ower bound : an estimate on a minimum amount of work needed to solve a given problem Examples: • number of comparisons needed to find the largest element in a set of n numbers • number of comparisons needed to sort an array of size n • nu

Huffman Trees Some useful definitions: • C ode word: Encoding a text that comprises n characters from some alphabet by assigning to each of the text’s characters some sequence of bits. This bits sequence is called code word • F ixed length encoding: Assigns to each character a bit string of the same length. • V ariable length encoding: Assigns code words of different lengths to different characters. Problem: How can we tell how many bits of an encoded text represent ith character? We can use prefix free codes • P r e f ix free code: In Prefix free code, no codeword is a prefix of a codeword of another character. • Binary prefix code : o The characters are associated with the leaves of a binary tree. o All left edges are labeled 0 o All right edges are labeled 1 o Codeword of a character is obtained by recording the labels on the simple path from the root to the character’s leaf. o Since, there is no simple path to a leaf that continues to anot