Team Members
Progress
Assignment 1
Project: LZW Compress
Introduction:
LZW stand for "Lempel–Ziv–Welch". It is a universal lossless data compression algorithm which is widely use in compressing software. It is widely used in image compress and Unix file compress. Here is a project example of LZW compressing written by c++. Here's the link for more details: https://codereview.stackexchange.com/questions/86543/simple-lzw-compression-algorithm
Basic Compile Command:(Linux)
g++ -std=c++0x lzw.c -o lzw
To Execute Projet
- Compress file:
./lzw -c file.txt
- Decopress file:
./lzw -d file.txt
Profile
We have compress and profile for 3 different size files. The runtime for each is shown below:
To see runtime for each function, see below:
Here is graphic:
Float profile:
Here is the float profile sample for compressing file which has size 54.3MB, float profile is changed to .txt and is simplified)
Project: Grep - Count Keyword in File
Introduction:
On the Linux system, we are very familiar with the Grep command. This is a similar project to that. But this one is more simple. It just counts how many times the keyword appears in the file. After compile the program, we run it as a command like this:
Here, it counts how many 'is' are there in file 'sample.txt'.
Profile:
We've make three different sizes of files to profile the program. The runtime of them show below:
To see runtime for functions, see below:
See graphic:
Profile via Visual Studio Sample:
Assignment 2
We are going to work on 'Grep' project.
Through the profile, we can see that the most cost of the runtime is 'grep()' and 'convert_char_to_string()' functions. I first look at function 'convert_char_to_string()'. I think it's no necessary to use this function, so I remove it.
As file size growing up, which means more characters in file, the runtime of 'grep()' grows much more faster than the other functions. So we are going to work on 'grep()' function.
Let's going through grep() function:
We can see, there're two for loop in grep() function. In loop is inside another. Which mean it's kind of O(n^m) runtime function. That's why it cost a lot of time to run.