Code Monkey home page Code Monkey logo

mit-ocw-6.006's Introduction

MIT-OCW-6.006 (Fall 2011)

Problem set 1. Peak finding

In the filealgorithms.py, there are four different algorithms whichhave been written to solve the peak-finding problem, only some of which are correct. Your goal isto figure out which of these algorithms are correct and which are efficient.

Problem set 2. Digital circuit simulation.

A combinational circuit is made up of gates, which are devices that take Boolean (True/ 1 andFalse/0) input signals, and output a signal that is a function of the input signals. Gates take sometime to compute their functions, so a gate’s output at timeτreflects the gate’s inputs at time τ−δ, where δ is the gate’s delay. For the purposes of this simulator, a gate’s output transitions between0 and 1 instantly. Gates’ output terminals are connected to other gates’ inputs terminals by wires that propagate the signal instantly without altering it.

The circuit simulator takes an input file that describes a circuit layout, including gates’ delays, probes (indicating the gates that we want to monitor the output), and external inputs. It then simulates the transitions at the output terminals of all the gates as time progresses. It also outputs transitions at the probed gates in the order of the timing of those transitions.This problem will walk you through the best known approach for fixing performance issues in a system. You will profile the code, find the performance bottleneck, understand the reason behind it, and remove the bottleneck by optimizing the code.

Solved with implementation of priority queue algorithm. Priority queue data structure takes O(0) time to find Min element.

Problem set 3. Digital circuit layout.

A chip consists of logic gates, whose input and output terminals are connected by wires (very thin conductive traces on the silicon substrate). AMDtel’s high-yield manufacturing process only allows for horizontal or vertical wires. Wires must not cross each other, so that the circuit will function according to its specification. This constraint is checked by the software tool that you will optimize. The topologies required by complex circuits are accomplished by having dozens of layers of wires that do not touch each other, and the tool works on one layer at a time.

The method that has the performance bottleneck is called from the CrossVerifier class. Upon reading the class, it seems that the original author was planning to implement a sweep-line algorithm, but couldn’t figure out the details, and bailed and implemented an inefficient method at the last minute. Fortunately, most of the infrastructure for a fast sweep-line algorithm is still in place.Furthermore, you notice that the source code contains a trace of the working sweep-line algorithm, in the good trace.jsonp file. Sweep-line algorithms are popular in computational geometry. Conceptually, such an algorithm sweeps a vertical line left to right over the plane containing the input data, and performs operations when the line “hits” point of interest in the input. This is implemented by generating an array containing all the points of interest, and then sorting them according to their position along the horizontal axis (x coordinate).

Solved with implementation of Binary search tree, AVL tree + range query.

Problem set 4. Matching DNA Sequences

mit-ocw-6.006's People

Contributors

grinyahoo avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.