The repository contains the code of OJ and Project in Sustech CS216 2022
This week OJ questions' topic is stable matching, concentrating on one-to-one matching and one-to-many matching.
OJ questions in this week are about using greedy algorithm wisely.
The question A is about the simulation of the machanism of LRU
The question B is about the shortest path of the weighted graph and reverse of modulo.
The question A is about the greedy algorithm
The question B is about the transformation between Manhattan Distanc and Chebyshev Distance
The question A is about the Peano curve, which is the advanced level of Hilbert curve, quite interesting.
The question B is the application of segment Tree, which is quite useful in updating the interval value and finding the sum of a given interval in
The question A is about the simple dynamic planning and searching with memorization.
The question B is about the dynamic planning and interesting derivation of formula.
The question A is about the simple count dp.
The question B is about the difficult DP with CDQ divide
The question A is about the application of BellmanFord algorithm to find the shortes path in a negtive weighted graph.
The question B is about the wildcast matching of a string, which is also about the dynamic planning.
The question A is about the DP algorithm plus game algorithm and memoized search.
The question B is about the DP algorithm and improve the combination calculation using pascal triangle and powers array.
The question A and B both use the Dinic Algorithm to solve the network flow problem. And the construction of relation grapg of question B is hard to build.
The question A is about using random algorithm to optimize the knapsack problem to make the time complexity to reach O(N).
The question B is about using random algorithm to optimize the problem of finding the closest pair of a 3D point cloud, which can be optimized from O(NlogN) to O(N).
Please write a simple report to introduce the caching mechanism used in modern CPUs. Try to answer the following, but not limit to, questions in your report.
-
What is the cache performance measurement?
-
What are the cache replacement policies, LRU?
-
Any other policies and methods to improve performance?
The report should not exceed 2 pages in font size 10.
In this assignment, I have designed, implemented and analyzed the algorithm to find the closest pair of 3D point cloud.
The procedure of designing the algorithm has been introduced detailedly.
What's more, I have uploaded the implemented code to the directory “Assignment/Assignment2/closed-pair.cpp”
In this assignment, I just called the FFT in Python to complete it.
In this assignment, I wrote a report on AI Poetry. In the report, I firstly introduce the modern technology on AI poetry, and put forward my viewpoint on the field.
Implement a ZIP compressor using Java or C/C++.
- It can compress one sinle file into a zip file. Multiple-file compression is optional.
- The compressed zip file can be decompressed successfully by professional zip software. Such as it can be decompressed by double clicking in Windows/MacOS.
- You can implement the commonly used compression algorithm DEFLATE and static Huffman in DEFLATE.
- Please submit by the deadline. Otherwise 0 score. Sumit your report in PDF which clearly introduces your implementation and the highlights, and submit your source code in a zip file.
- If you reference some source code from others, please state it clearly in the report and give references at the end of the report.
Complete the zero-compress convertion of simple txt file (only contains "Hello World!") to zip file, which can be decompressed by OS.
Know the meaning of each segment of a zip file.
Complete the zero-compress convertion of simple file (not only contains "Hello World!!!") to zip file, which can be decompressed by OS
replace each segment of zip file to what it should be.
The key segments are:
- last modified time and date (quite troublesome)
- the crc32 encryption
- the size of file before and after compressing.
- offset of start of central directory with respect to the starting disk number
- implement the LZ77 algorithm but the alogorithm have not been tested.
- Implement the bit stream emitter and LZ77 encoding.
- Tomorrow the algorithm will be tested and static Huffman will be implemented.
- Fighting
- verify the LZ77 algorithm and implement the static Huffman compression.
- Huffman has been tested, meaning that deflate has been done
- Next I will combine the header and deflate algorithm, good luck!
- Correct some Bugs and combine the header and deflate successfully~
- complete the zip deflate using static huffman compression~ Hurray!
- Next I will improve the algorithm and do many experiments~
- improve the structure of the zip files, dividing them into three files——zip.hpp, zip.cpp, main.cpp and write CMakeLists.txt to run them easily.
- update some bugs(central directory size bug ~)
The zip.hpp file is header file, and the zip.cpp is the source file.
- Going to fix the bug that I can not compress the file whose size is larger than 20KB
Your device should support the minimum cmake version of 3.16 and the C++ version is C++17.
just arrange the file structure as shown, then run the
cmake . && makecommands so that the executable file named zip will be generated.
Then run ./zip and input the source txt file you want to compress and input the zip file name you want to generate, then a zip file will be generated.
- fix the bug that the Chinese text file cannot be compressed.
- do some experiments and update report.