Skip to content

Instantly share code, notes, and snippets.

View ouwenshi's full-sized avatar

Ouwen Shi ouwenshi

2 followers · 0 following
  • Chicago, IL
View GitHub Profile
@ouwenshi
ouwenshi / string_find.cpp
Created April 24, 2018 15:00
Find a string S in a given given string.
#include <iostream>
using namespace std;
int findSubString(string s, string sub, const string &S, int pos, int cur) {
if (sub.empty())
return pos;
else if (s.empty())
return -1;
@ouwenshi
ouwenshi / n_queens.cpp
Created April 16, 2018 03:57
A recursive solution of n-Queens problem.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<bool>> board;
vector<bool> columnEmpty, leftDiagEmpty, rightDiagEmpty;
bool isSafe(int r, int c, int n) {
return columnEmpty[c] && leftDiagEmpty[r + c] && rightDiagEmpty[n - 1 + r - c];
@ouwenshi
ouwenshi / sll.cpp
Last active April 24, 2018 15:07
An implementation of singly linked list.
#include <iostream>
#include <algorithm>
using namespace std;
template <class T>
struct Node {
T key;
Node *next;
Node() {}
@ouwenshi
ouwenshi / reverse_string.cpp
Created March 2, 2018 05:31
Reverse any given string.
#include <iostream>
#include <string>
using namespace std;
void reverse_string(string &sentence) {
for (int i = 0; i < sentence.size() / 2; i++)
swap(sentence[i], sentence[sentence.size() - 1 - i]);
}
@ouwenshi
ouwenshi / bubble_sort.cpp
Created March 2, 2018 02:53
An implementation of bubble sort.
#include <iostream>
#include <vector>
using namespace std;
template <class T>
void bubble_sort(vector<T> &input_array) {
for (int i = input_array.size() - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
if (input_array[j] > input_array[j + 1])
@ouwenshi
ouwenshi / quick_sort.cpp
Created March 1, 2018 22:01
An implementation of quick sort.
#include <iostream>
#include <vector>
using namespace std;
template <class T>
int partition_array(int low, int high, vector<T> &input_array) {
int i = low;
for (int j = low; j < high; j++)
if (input_array[j] <= input_array[high])
@ouwenshi
ouwenshi / max_subarray.cpp
Created March 1, 2018 18:38
An implementation of maximum-subarray problem.
#include <iostream>
#include <vector>
using namespace std;
template<class T>
struct Results {
int low, high;
T sum;
};
@ouwenshi
ouwenshi / merge_sort.cpp
Last active March 2, 2018 15:47
An implementation of merge sort.
#include <iostream>
#include <vector>
using namespace std;
template <class T>
void merge_two_sorted_arrays(int low, int high, int mid, vector<T> &input_array) {
vector<T> partial_array;
int m = low, n = mid + 1;
while (m <= mid && n <= high) {
@ouwenshi
ouwenshi / array_reduction_multiplier.v
Created February 19, 2018 20:58
An 64-bit array reduction multiplier using 4:2 reducer.
`define INPUTSIZE 32 //hard-coded: don't change
`define FINALADDER 2 //choose from CSA, CLA and prefix CLA (need to include corresponding functions)
module Array_Reduction_Multiplier_64b(X,Y,Z);
input [`INPUTSIZE - 1:0] X;
input [`INPUTSIZE - 1:0] Y;
output [`INPUTSIZE * 2 - 1:0] Z;
wire [(`INPUTSIZE * 2) * (`INPUTSIZE * 2 - 1) - 1:0] addend;
wire [`INPUTSIZE * `INPUTSIZE - 1:0] bit_and;
@ouwenshi
ouwenshi / carry_save_multiplier.v
Last active February 19, 2018 20:54
An n-bit carry save multiplier.
`define INPUTSIZE 32 //set the input size n
module Carry_Save_Multiplier(X,Y,Z);
input [`INPUTSIZE - 1:0] X;
input [`INPUTSIZE - 1:0] Y;
output [`INPUTSIZE * 2 - 1:0] Z;
wire [`INPUTSIZE * `INPUTSIZE - 1:0] partial_sum;
wire [`INPUTSIZE * (`INPUTSIZE - 1) - 1:0] and_out;